package ch04
{

	public class AStar
	{
		private var _open:Array; //储待考察表
		private var _closed:Array; //已考察表
		private var _grid:Grid; //网格
		private var _endNode:Node; //开始节点
		private var _startNode:Node; //终点节点
		private var _path:Array;
		//private var _heuristic:Function = manhattan;
		//private var _heuristic:Function = euclidian;
		private var _heuristic:Function = diagonal;
		private var _straightCost:Number = 1.0;
		private var _diagCost:Number = Math.SQRT2;


		public function AStar()
		{
		}

		public function findPath(grid:Grid):Boolean
		{
			_grid = grid;
			_open = new Array();
			_closed = new Array();

			_startNode = _grid.startNode;
			_endNode = _grid.endNode;

			/**
			 * 我们来看一下起点的代价是怎么计算出来的。因为g值的定义是从起点到当前点的消耗，
			   这时起点就是当前点，让当前节点的 g 值为 0。接下来选用任一一种估价方法，传入起点，
			   将会返回到终点的估价，这就是h。最后h+g 得到这个点的总代价。
			   接下来是这个类的关键，search 方法。它的作用是挨个计算起点.
			 */
			_startNode.g = 0;
			_startNode.h = _heuristic(_startNode);
			_startNode.f = _startNode.g + _startNode.h;

			return search();
		}

		/**
		 * 作用是挨个计算起点节点一直到终点节点，计算出最佳路径
		 * @return
		 */
		public function search():Boolean
		{
			var node:Node = _startNode;
			while (node != _endNode)
			{
				//计算需要检查网格的起始点和终点
				//通过Math.min 和Math.max 确保了检查的节点永远在网格里面。
				var startX:int = Math.max(0, node.x - 1);
				var endX:int = Math.min(_grid.numCols - 1, node.x + 1);
				var startY:int = Math.max(0, node.y - 1);
				var endY:int = Math.min(_grid.numRows - 1, node.y + 1);

				for (var i:int = startX; i <= endX; i++)
				{
					for (var j:int = startY; j <= endY; j++)
					{
						var test:Node = _grid.getNode(i, j);
						//对于每一个节点来说，如果它是当前节点或不可通过的，就忽略它，直接跳到下一个：
						//拐角情况：!_grid.getNode(node.x, test.y).walkable || !_grid.getNode(test.x, node.y).walkable 如果这个点的对角是不能通过的，跳过这个点。
						if (test == node || !test.walkable || !_grid.getNode(node.x, test.y).walkable || !_grid.getNode(test.x, node.y).walkable)
						{
							continue;
						}
						var cost:Number = _straightCost;
						//对角情况
						if (!((node.x == test.x) || (node.y == test.y)))
						{
							cost = _diagCost;
						}
						/**
						 * 计算从开始节点到测试节点的代价
						   （g），方法是当前节点的 g 值加上当前节点到测试节点的代价。简化以后就是水平、竖直方
						   向直接加上_straightCost，对角加上_diagCost.h 通过估价函数计算，然后g 和 h 求和，得
						   到f（总代价）。
						   costMultiplier为节点的代价,举个例子，土路节点肯定比高速公路的代价大，沼泽或是高山节点代价可能大很多。
						 */
						var g:Number = node.g + cost * test.costMultiplier;
						var h:Number = _heuristic(test);
						var f:Number = g + h;
						/**
						 * 下面这个部分有一点小技巧，之前我们并没有谈到。开始的时候，我说过如果一个节点
						   在待考察表/已考察表里，因为它已经被考察过了，所以我们不需要再考察。不过这次计算出
						   的结果有可能小于你之前计算的结果（比如说，上次计算时是对角，而这次确是上下或左右
						   关系，代价就小一些）。所以，就算一个节点在待考察表/已考察表里面，最好还是比较一下
						   当前值和之前值之间的大小。具体做法是比较测试节点的总代价与以前计算出来的总代价。
						   如果以前的大，我们就找到了更好的节点，我们就需要重新给测试点的f，g，h 赋值，同时，
						   我们还要把测试点的父节点设为当前点。这就要我们向后追溯。

						   如果测试节点不再待考察表/已考察表里面，我们只需要赋值给f，g，h 和父节点。然后
						   把测试点加到待考察表，然后是下一个测试点，找出最佳点。
						 */
						if (isOpen(test) || isClosed(test))
						{
							if (test.f > f)
							{
								test.f = f;
								test.g = g;
								test.h = h;
								test.parent = node;
							}
						}
						else
						{
							test.f = f;
							test.g = g;
							test.h = h;
							test.parent = node;
							_open.push(test);
						}
					}
				}
				var numloop:int = _open.length;
				for (var o:int = 0; o < numloop; o++)
				{
				}
				_closed.push(node);
				if (_open.length == 0)
				{
					trace("no path found");
					return false;
				}
				/**
				 * 如果待考察表上面有很多节点，我们需要找到最优的（总代价最小的那个）。可以按列表里元素的f 值排序，最后的那个就是最好的。
				 */
				_open.sortOn("f", Array.NUMERIC);
				node = _open.shift() as Node;
			}
			buildPath();
			return true;
		}

		private function buildPath():void
		{
			_path = new Array();
			var node:Node = _endNode;
			_path.push(node);
			while (node != _startNode)
			{
				node = node.parent;
				_path.unshift(node);
			}
		}

		public function get path():Array
		{
			return _path;
		}

		private function isOpen(node:Node):Boolean
		{
			var numloop:int = _open.length;
			for (var i:int = 0; i < numloop; i++)
			{
				if (_open[i] == node)
				{
					return true;
				}
			}
			return false;
		}

		private function isClosed(node:Node):Boolean
		{
			var numloop:int = _closed.length;
			for (var i:int = 0; i < numloop; i++)
			{
				if (_closed[i] == node)
				{
					return true;
				}
			}
			return false;
		}

		/**
		 * 做曼哈顿估价法(Manhattan heuristic),它忽略所有的对角移动，只添加起点
		   节点和终点节点之间的行、列数目。就像你在曼哈顿的大街上一样，比如说，你在（5，40），
		   到（8，43），你必须先在一个方向上走过 3 个节点，然后另一个方向上的 3 个节点。有可能
		   是先横走完，在竖走完，反之亦然；或者横、竖、横、竖、横、竖，每边都要走3 个。
		 * @param	node
		 * @return
		 */
		private function manhattan(node:Node):Number
		{
			return Math.abs(node.x - _endNode.x) * _straightCost + Math.abs(node.y + _endNode.y) * _straightCost;
		}

		/**
		 * 是几何估价法（ Euclidian heuristic）它 计算出两点之间的直线距离，本质公式为勾股定理A 2 +B 2 =C 2 。
		 * @param	node
		 * @return
		 */
		private function euclidian(node:Node):Number
		{
			var dx:Number = node.x - _endNode.x;
			var dy:Number = node.y - _endNode.y;
			return Math.sqrt(dx * dx + dy * dy) * _straightCost;
		}

		/**
		 * 对角线估价法(Diagonal heuristic),这个方法是三个估价方法里面最精确的，如果没有障碍，它将返回实际的消耗。
		 * @param	node
		 * @return
		 */
		private function diagonal(node:Node):Number
		{
			var dx:Number = Math.abs(node.x - _endNode.x);
			var dy:Number = Math.abs(node.y - _endNode.y);
			var diag:Number = Math.min(dx, dy);
			var straight:Number = dx + dy;
			return _diagCost * diag + _straightCost * (straight - 2 * diag);
		}

		public function get visited():Array
		{
			return _closed.concat(_open);
		}
	}
}
